#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<cstdlib>
#include<string>
#include<sstream>
using namespace std;
//int main()
//{
//	string mystr;
//	getline(cin, mystr);
//	if (mystr == "FD 100")
//	{
//		cout << 100;
//	}
//
//	return 0;
//}
//#include<iostream>
//#include<string>
//#include<sstream>
//using namespace std;
//int logo()
//{
//	char c;
//	int distance = 0;
//	int k = 0;
//	int v = 0;
//	string str;
//	while (cin >> c)
//	{
//		if (c == ']')
//		{
//			break;
//		}
//		cin >> str >> k;
//		if (c == 'R')
//		{
//			v = getchar();
//			//cout << getchar() << endl;
//			distance += k * logo();
//			v = getchar();
//			//cout << getchar() << endl;
//
//		}
//		else if (c == 'F')
//		{
//			v = getchar();
//			//cout << getchar() << endl;
//			distance += k;
//		}
//		else if (c == 'B')
//		{
//			v = getchar();
//			//cout << getchar() << endl;
//
//			distance -= k;
//		}
//		if (v == int(']'))
//		{
//			break;
//		}
//	}
//	return distance;
//}
//int main()
//{
//	cout << abs(logo()) << endl;
//	return 0;
//}
#include<iostream>
using namespace std;
void merge(int* arr, int* tempArr, int left, int mid, int right)
{
	int l_pos = left;
	int r_pos = mid + 1;
	int pos = left;
	while (l_pos <= mid && r_pos <= right)
	{
		if (arr[l_pos] < arr[r_pos])
		{
			tempArr[pos++] = arr[l_pos++];
		}
		else
		{
			tempArr[pos++] = arr[r_pos++];
		}
	}
	while (l_pos <= mid)
	{
		tempArr[pos++] = arr[l_pos++];
	}
	while (r_pos <= right)
	{
		tempArr[pos++] = arr[r_pos++];
	}

	while (left <= right)
	{
		arr[left] = tempArr[left];
		left++;
	}
}
void msort(int* arr, int* tempArr, int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2;
		msort(arr, tempArr, left, mid);
		msort(arr, tempArr, mid + 1, right);
		merge(arr, tempArr, left, mid, right);
	}
}
void merge_sort(int* arr, int n)
{
	int* tempArr = (int*)malloc(n * sizeof(int));
	if (tempArr)
	{
		msort(arr, tempArr, 0, n - 1);
		free(tempArr);
	}
	else
	{
		printf("error");
	}
}
int main()
{
	int arr[10] = { 9,3,4,6,1,2,5,7,8,10 };
	merge_sort(arr, 10);
	for (int i = 0; i < 10; i++)
	{
		cout << arr[i] << " ";
	}
	return 0;
}